package LeetCode.month01.day04;

import java.util.Arrays;
import java.util.HashMap;

public class No41 {
    public static void main(String[] args) {
        int[] nums = {-1,2,0};
        System.out.println(firstMissingPositive(nums));
        
    }


    public static int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
//        int left = 0,right=0;
//        HashMap<Integer,Integer> map = new HashMap<>();
//        for (int i = 0; i < nums.length; i++) {
//            right = Math.max(right,nums[i]);
//            left = Math.min(left,nums[i]);
//            map.put(nums[i],i);
//        }
//        //System.out.println(left);
//        //System.out.println(right);
//        if(left>1) return left-1;
//        for (int i = 1; i <=right; i++) {
//            if(!map.containsKey(i)) return i;
//        }
//        return right+1;
    }
}
